In the latter half of the twentieth century, there began a phenomenon known as the information revolution. While the information revolution is a historical development broader in scope than any one event or machine, no single device has come to represent the information revolution more than the digital electronic computer. The development of computer systems has surely been a revolution. Each year, computer systems grow faster, store more data, and provide more applications to their users.
A modern computer system typically comprises one or more central processing units (CPU) and supporting hardware necessary to store, retrieve and transfer information, such as communication buses and memory. It also includes hardware necessary to communicate with the outside world, such as input/output controllers or storage controllers, and devices attached thereto such as keyboards, monitors, tape drives, disk drives, communication lines coupled to a network, etc. The CPU or CPUs are the heart of the system. They execute the instructions which comprise a computer program and directs the operation of the other system components.
From the standpoint of the computer's hardware, most systems operate in fundamentally the same manner. Processors are capable of performing a limited set of very simple operations, such as arithmetic, logical comparisons, and movement of data from one location to another. But each operation is performed very quickly. Sophisticated software at multiple levels directs a computer to perform massive numbers of these simple operations, enabling the computer to perform complex tasks. What is perceived by the user as a new or improved capability of a computer system is made possible by performing essentially the same set of very simple operations, but using software having enhanced function, along with faster hardware.
In the very early history of the digital computer, computer programs which instructed the computer to perform some task were written in a form directly executable by the computer's processor. Such programs were very difficult for a human to write, understand and maintain, even when performing relatively simple tasks. As the number and complexity of such programs grew, this method became clearly unworkable. As a result, alternate forms of creating and executing computer software were developed.
The evolution of computer software has led to the creation of sophisticated software development environments. These environments typically contain a range of tools for supporting the development of software in one or more high-level languages. For example, interactive source editors support the initial generation of source code by a developer. Source databases may support collections of source modules or source objects, which serve as the component parts of software applications. Front-end compiler/debuggers perform simple semantic verification of the source and reduction to a standard form. Back-end or optimizing compilers generate machine executable object code from the standard form, and may optimize the performance of this code using any of various optimization techniques. Build utilities assemble multiple object code modules into fully functioning computer programs.
Among the tools available in many such programming development environments are a range of diagnostic and debug tools. Although compilers and debuggers used during the initial creation and compilation phases of development can identify certain obvious inconsistencies in source code and produce object code conforming to the source, they can not verify the logic of a program itself, or that the program makes use of available resources in an efficient manner. This is generally accomplished by observing the behavior of the program at “run-time”, i.e., when executed under real or simulated input conditions. Various tools exist which collect data concerning the run-time behavior of a computer program. Analytical tools assist the programmer in analyzing the run-time data to find logical errors, inefficiencies, or other problems with the code.
Many tools exist for collecting run-time data, but in general the data collected may be categorized as either trace data or sample data. Trace data is data which is collected in response to some specific program state. Typically, trace data is collected by “instrumenting” the programming code, meaning that special-purpose instructions are inserted in the code at key locations. These instructions may cause the collection of trace data whenever such an instruction is encountered during execution. The type and amount of trace data collected in response to encountering such an instruction may vary, and the collection of trace data may be conditional on other state variables in addition to the instruction. Sampled data, on the other hand, is typically data which is collected at pre-established sampling intervals during program execution, the sampling intervals being independent of program state. As in the case of trace data, the amount and type of data that is collected at a sampling interval may vary.
Data collected by run-time collection tools might include various program parameters, such as code paths taken, procedures and functions called, values of key variables, storage accesses, memory allocations, and so forth. One of the problems inherent in all data collection techniques, whether trace data or sample data is collected, is the overhead of collection, and in particular, the volume of data generated during program execution.
Trace data is useful in many circumstances, particularly for understanding a specific path which may be causing a problem. But trace data in particular has a tendency to impose a high overhead, which can in some circumstances distort the results. Where it is desirable to understand which portions of the code consume the most time during execution, the existence of frequently executed instrumentation points will by themselves cause a significant performance burden, and may distort results by making it appear as if a disproportionate share of time is spent executing code containing the instrumentation.
Sampled data is often useful for providing a statistical picture of the code routines in which the processor spends most of the execution time. Because sampled data is collected at fixed intervals which don't depend on program state, it is unlikely to significantly distort program performance. Moreover, because no instrumentation is required, sampled data can be easier to collect and consume less overhead.
Because sampled data is a “snapshot” collected independently of program state, it is sometimes difficult to understand a chain of events exhibited by the program. In particular, it can be difficult to understand the call history of a program from periodic “snapshots”. For example, if the data collected with each sampling interval is the currently executing instruction or procedure, then one does not know how that procedure was called. Even if the calling procedure is also included in the sampled data, this may provide only limited information concerning the call history. This problem can be particularly acute when analyzing programming code written in any of various object-oriented programming languages, which have complex call histories and procedures (“methods”) which are frequently called from different locations.
The overhead of sampling data depends on the amount of data collected with each sample. It would be possible to dump the entire contents of the stack every time a sample is collected in order to obtain a better understanding of call history, but this could potentially generate an enormous amount of data and impose significant program overhead. Moreover, because the stack size is variable, the overhead may be greater for some sampling intervals than others, which can distort the results.
As programs grow in size and complexity, and particularly as the use of object-oriented programming techniques grows, the task of analyzing and understanding run-time data, and in particular the task of analyzing and understanding call history from sample data taken during run-time, increases greatly in difficulty. A need exists for improved techniques for understanding program execution and call history data in a computer system.